package com.easy.leetcode.dp;
//494. 目标和
public class FindTargetSumWays494 {
    /**
     * 不重复放 -> 0-1背包->先物品，后背包且背包容量倒序遍历
     * 可重复放->完全背包->无序->组合问题->先物品，后背包且背包正序遍历
     *可重复放->完全背包->有序->排列问题->先背包，后物品遍历
     *
     * 求目标和，相当于把数组分为两部分，left-right =target
     * sum =left +right
     * left = (sum+target)/2
     * @param nums
     * @param target
     * @return
     */
    public int findTargetSumWays(int[] nums, int target) {
        int sum=0;
        //求和
        for (int num : nums) {
            sum+=num;
        }
        //余数为1 无解
        if ((sum+target)%2==1) {
            return 0;
        }
        if (Math.abs(target)>sum){
            return 0;
        }
        sum=(sum+target)/2;
        //填满容量为j的背包有的方法个数
        int[] dp = new int[sum+1];
        dp[0]=1;
        //不重复放-> 0-1背包->先遍历物品，后遍历背包，->背包倒序遍历，防止重复放
        for (int i = 0; i <nums.length ; i++) {
            for (int j = sum; j >=nums[i] ; j--) {
                dp[j]+=dp[j-nums[i]];
            }
        }
        return dp[sum];
    }
}
